//算法6.2 邻接表存储
#ifndef ALGRAPH_H_
#define ALGRAPH_H_

#include <stdio.h>
#include <stdlib.h>

#define Status int
#define OK 1
#define ERROR 0
#define OVERFLOW -1

#define MAX_V 20//最大顶点数目
#define eleType char 
#define GraphKind int
#define UndiGraph 1
#define DiGraph   2
#define IndirectedNet 3
#define DirectedNet 4

typedef struct VertexType  //顶点类型定义
{
    int code;  //顶点编号
    eleType info; //顶点其他信息
}VertexType;

typedef struct ArcNode  //边的结点结构类型
{
    int adjvex;  //该边的终点编号
    int weight;  //该边的权重（用于网）
    struct ArcNode *nextarc;  //指向下一条边的指针
}ArcNode;

typedef struct VexNode  //邻接表的顶点结构
{
    VertexType data;  //顶点信息
    ArcNode *firstarc;  //指向第一条与该顶点有关的边的指针
}VexNode;

typedef struct 
{
    VexNode VexsList[MAX_V];  //定义邻接表
    int vexnum,arcnum; //图包含的顶点数和边数
    VertexType vexs[MAX_V]; //存放顶点信息
    GraphKind type;
}ALGraph;

//基于邻接表表示法的无向图的创建
Status CreateGraph(ALGraph &G)
{
    scanf("%d %d",&G.vexnum,&G.arcnum);
    int i,j,k;

    //将每个顶点的信息先存入
    for(i=0;i<G.vexnum;i++)
    {
        scanf("%d %c",&G.vexs[i].code,&G.vexs[i].info);
    }

    //对邻接表的操作
    ArcNode* p;
    for(i=0;i<G.vexnum;i++)
    {
        G.VexsList[i].firstarc=NULL;  //邻接表初始化，所有单向链表均为空表
    }

    for(k=0;k<G.arcnum;k++)
    {
        scanf("%d %d",&i,&j);
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=j;     //这条边的起始点是i,终止点是j
        //头插法
        p->nextarc=G.VexsList[i].firstarc; //将这个结点p链接到表示i号顶点的链表后
        G.VexsList[i].firstarc=p;

        p=(ArcNode*)malloc(sizeof(ArcNode)); //由于是无向图，因此再创建一个表示对称的结点p
        p->adjvex=i;
        p->nextarc=G.VexsList[j].firstarc;
        G.VexsList[j].firstarc=p;
    }
    return OK;
}

//算法6.3 基于邻接表表示法的图的深度优先遍历

void DFS(ALGraph &G,int index,bool *visit);
void DFS_Visit(ALGraph &G)
{
    //图的深度优先遍历
    int i;
    bool visit[G.vexnum];
    for(i=0;i<G.vexnum;i++)
    {
        //辅助数组初始化，初始条件下所有顶点均未被访问
        visit[i]=false;
    }

    for(i=0;i<G.vexnum;i++)
    {
        if(visit[i]==false)
        {
            DFS(G,i,visit);
        }
    }
}

//以index为起始点的深度优先遍历
void DFS(ALGraph &G,int index,bool *visit)
{
    ArcNode* p;
    visit[index]=true; //将起始点标记为已被访问的状态
    printf("%d %c\n",G.vexs[index].code,G.vexs[index].info);  //输出起始点的信息
    p=G.VexsList[index].firstarc;  //指针p指向起始点的第一个邻接点
    while(p)
    {
        //遍历起始点的所有邻接点，若邻接点已经被访问过，那么p继续向后访问
        //否则以当前邻接点为新的起始点递归进行深度优先遍历
        if(visit[p->adjvex]==false)
        {
            DFS(G,p->adjvex,visit);
        }
        p=p->nextarc;
    }
}

//算法6.5 基于邻接表表示法的图的广度优先遍历
void BFS_Visit(ALGraph &G)
{
    //广度优先遍历
    int i;
    bool visit[G.vexnum];
    for(i=0;i<G.vexnum;i++)
    {
        //辅助数组初始化，初始条件下所有顶点均未被访问
        visit[i]=false;
    }
    for(i=0;i<G.vexnum;i++)
    {
        if(visit[i]==false)
        {
            BFS(G,i,visit);
        }
    }
}

//以index为起始点的广度优先遍历
void BFS(ALGraph &G,int index,bool *visit)
{
    ArcNode* p;
    int Qu[MAX_V];  //定义队列
    int front,rear;
    front=rear=0;
    Qu[rear++]=index;  //起始点入队
    visit[index]=true;
    while(front!=rear)
    {
        int  i;
        i=Qu[front];  //队头元素出队
        front=(front+1)%MAX_V;
        printf("%d %c\n",G.vexs[index],G.vexs[index].info);
        p=G.VexsList[index].firstarc; //p指向当前队头顶点的第一个邻接点
        while(p)
        {
            //遍历当前队头顶点的所有邻接点，若邻接点已被访问，则p继续向后遍历
            //否则入队，并且标记为已访问状态，防止重复入队
            if(visit[p->adjvex]==false)
            {
                Qu[rear]=p->adjvex;
                rear=(rear+1)%MAX_V;
                visit[p->adjvex]=true;
            }
            p=p->nextarc;
        }
    }

}

//图的遍历算法的应用举例
//算法6.7 计算无向图的连通分量的个数(DFS)
int GetCCNum(ALGraph &G)
{
    //求无向图的连通分量的个数
    int count=0;  //统计连通分量个数
    int i;
    bool visit[G.vexnum];
    for(i=0;i<G.vexnum;i++)
    {
        visit[i]=false;
    }

    for(i=0;i<G.vexnum;i++)
    {
        if(visit[i]==false)
        {
            DFS(G,i,visit);
            count++;        //调用DFS的次数即为图的连通分量的个数
        }
    }
}

//算法6.8 判断无向图的连通性(DFS)
Status IsConnectedGraph(ALGraph &G)
{
    //判断无向图是否连通
    int i;
    bool visit[G.vexnum];
    for(i=0;i<G.vexnum;i++)
    {
        visit[i]=false;
    }

    DFS(G,0,visit);//以第一个顶点为起始点（任意起点均可）调用一次DFS
    for(i=0;i<G.vexnum;i++)
    {
        if(visit[i]==false)
        {
            return ERROR;
        }
    }
    return OK;
}

//算法6.9 判断顶点之间的连通性(DFS)
Status IsConnected(ALGraph &G,int u,int v)
{
    int i;
    bool visit[G.vexnum];
    for(i=0;i<G.vexnum;i++)
    {
        visit[i]=false;
    }
    DFS(G,u,visit);    //以u为起点，调用一次DFS
    if(visit[v]==false)  //如果v未被访问，则说明二者不连通
    {
        return ERROR;
    }
    else{
        return OK;
    }
}

//算法6.10 求图中距离某个顶点最远的任意一个顶点(BFS)
int FindMaxDist(ALGraph &G,int v)
{
    ArcNode *p;
    int Qu[MAX_V],visit[MAX_V];
    int front,rear;
    front=rear=0;
    for(int i=0;i<G.vexnum;i++)
    {
        visit[i]=0;
    }
    Qu[rear++]=v;
    visit[v]=1;
    int i;
    while(front!=rear)
    {
        i=Qu[front];
        front=(front+1)%MAX_V;
        p=G.VexsList[i].firstarc;
        while(p)
        {
            if(visit[p->adjvex]=0)
            {
                visit[p->adjvex]=1;
                Qu[rear]=p->adjvex;
                rear=(rear+1)%MAX_V;
            }
            p=p->nextarc;
        }
    }
    return i; //i是最后出队的结点，它就是距离顶点v最远的结点
}

//算法6.10 求图中两个顶点间的全部简单路径(DFS)
void FindPath(ALGraph &G,int u,int v,int *path,int d)
{
    //d表示路径的长度，初始值为0
    ArcNode *p;
    path[d]=u;  //将起点放入路径
    bool visit[MAX_V];
    for(int i=0;i<G.vexnum;i++)
    {
        visit[i]=false;
    }
    visit[u]=true;

    if(u=v) //如果当前起始点已经等于终止点，说明已经找到一条路径
    {
        for(int i=0;i<=d;i++)
        {
            printf("%d ",path[i]);
        }
        printf("\n");
    }

    else{
        p=G.VexsList[u].firstarc;
        while(p)
        {
            if(visit[p->nextarc]=false)
            {
                FindPath(G,p->adjvex,v,path,d+1);
                visit[p->adjvex]=true;
            }
            p=p->nextarc;
        }
    }
}

#endif